import pandas as pd
import numpy as np
import math
import matplotlib.pyplot as plt
from scipy.spatial.kdtree import KDTree
from sklearn.cluster import DBSCAN

def readDataSet(filename, div=2):
    data = np.loadtxt(filename)
    return data

def readDataSetwithLabel(filename, div=2):
    matrix = np.loadtxt(filename)
    label = matrix[:, -1]
    matrix = np.delete(matrix, -1, axis=1)
    return matrix, label

def readLabel(filename):
    data = pd.read_csv(filename, header=None)
    matrix = np.array(data)
    return matrix

def getKNN(matrix, k):
    '''
    获得knn连接图
    :param matrix:  坐标信息
    :param k: k个最近邻
    :return: dd: 距离矩阵，最近的k个点的距离
    :return: ii: 索引矩阵，最近的k个点的索引
    '''
    kd_tree = KDTree(matrix)
    dd, ii = kd_tree.query(matrix, k = k+1)
    dd = np.delete(dd, 0, axis=1)
    ii = np.delete(ii, 0, axis=1)
    return dd, ii

def get_dist(location):
    length = location.shape[0]
    dist = np.zeros((length, length))
    begin = 0
    while begin < length - 1:
        end = begin + 1
        while end < length:
            d = np.linalg.norm(location[begin] - location[end])
            dist[begin][end] = d
            dist[end][begin] = d
            end = end + 1
        begin = begin + 1
    return dist

def get_w(dd, k1):
    length = len(dd)
    w = np.zeros((length, 1), dtype=float)
    for i in range(length):
        weight = 0
        for j in range(k1):
            weight = weight + dd[i][j]
        w[i] = weight
    return w

def get_wr_ration(ind_1, ind_2, w):
    if w[ind_1] > w[ind_2]:
        return 1.0 * w[ind_2] / w[ind_1]
    else:
        return 1.0 * w[ind_1] / w[ind_2]

def ExpandCluster(ind, sr, cluster_id, cluster, ii, w):
    cluster_id = cluster_id + 1
    cluster[ind] = cluster_id
    seedlist = []
    begin = 0
    end = 0
    for j in ii[ind]:
        if cluster[j] == -1:
            wr_ration = get_wr_ration(ind, j, w)[0]
            if wr_ration >= sr:
                cluster[j] = cluster_id
                seedlist.append(j)
                end = end + 1
    while begin < end:
        the_ind = seedlist[begin]
        for j in ii[the_ind]:
            if cluster[j] == -1:
                wr_ration = get_wr_ration(the_ind, j, w)[0]
                if wr_ration >= sr:
                    cluster[j] = cluster_id
                    seedlist.append(j)
                    end = end + 1
        begin = begin + 1
    return cluster_id

def fix_procedure(result, ii, w, sr, k):
    length = len(result)
    for i in range(length):
        points = np.where(result == result[i])
        if len(points[0]) < k:
            for j in ii[i]:
                if result[i] != result[j]:
                    wr_ratio = get_wr_ration(i, j, w)[0]
                    if wr_ratio >= 0.8 * sr:
                        result[i] = result[j]
                        break
    themax = np.max(result)
    for i in range(themax):
        points = np.where(result == i + 1)[0]
        if len(points) == 0:
            continue
        elif len(points) < k:
            for p in points:
                result[p] = -1
    return

def vcda(matrix, k, k1, sr):
    cluster_id = 0
    dd, ii = getKNN(matrix, k)
    w = get_w(dd, k1)
    length = matrix.shape[0]
    result = np.ones((length , 1), dtype=int) * -1
    for i in range(length):
        if result[i] == -1:
            cluster_id = ExpandCluster(i, sr, cluster_id, result, ii, w)
    fix_procedure(result, ii, w, sr, k)
    return result

def plotResult(location, result, filename):
    length = len(result)
    markers = ['.', '*', '+', 'x', '^']
    colors = ['maroon', 'red', 'peru', 'gold', 'olive', 'yellowgreen', 'lawngreen', 'springgreen']
    colors = colors + ['turquoise', 'teal', 'deepskyblue', 'dodgerblue', 'royalblue', 'navy']
    colors = colors + ['slategrey', 'orchid', 'm', 'deeppink', 'crimson']
    plt.figure(figsize=(10, 10))

    title = "VBDC Clustering Result"
    plt.title(title)
    for i in range(0, length):
        index = int(result[i])
        if index == -1:
            plt.plot(location[i][0], location[i][1], color=(0,0,0),  marker='.')
        else:
            plt.plot(location[i][0], location[i][1], color=colors[index%19], marker=markers[index%5])
    plt.xlabel('Attribute 1'), plt.ylabel('Attribute 2')

    plt.savefig(filename)
    plt.show()

if __name__ == '__main__':
    input_file = 'Jain.txt'
    output_file = 'result.txt'
    output_img = 'result.png'
    dim = 2
    is_with_label = 1
    k = 8
    k1 = 2
    sr = 0.61
    matrix, label = readDataSetwithLabel(input_file, dim)
    result = vcda(matrix, k, k1, sr)
    plotResult(matrix, result, output_img)
    np.savetxt(output_file, result)


